Probing the large deviations for the beta random walk in random medium.

We consider a discrete-time random walk on a one-dimensional lattice with space- and time-dependent random jump probabilities, known as the beta random walk. We are interested in the probability that, for a given realization of the jump probabilities (a sample), a walker starting at the origin at time t=0 is at position beyond ξsqrt[T/2] at time T. This probability fluctuates from sample to sample and we study the large-deviation rate function, which characterizes the tails of its distribution at large time T≫1. It is argued that, up to a simple rescaling, this rate function is identical to the one recently obtained exactly by two of the authors for the continuum version of the model. That continuum model also appears in the macroscopic fluctuation theory of a class of lattice gases, e.g., in the so-called KMP model of heat transfer. An extensive numerical simulation of the beta random walk, based on an importance sampling algorithm, is found in good agreement with the detailed analytical predictions. A first-order transition in the tilted measure, predicted to occur in the continuum model, is also observed in the numerics.

First-passage area distribution and optimal fluctuations of fractional Brownian motion.

We study the probability distribution P(A) of the area A=∫_{0}^{T}x(t)dt swept under fractional Brownian motion (fBm) x(t) until its first passage time T to the origin. The process starts at t=0 from a specified point x=L. We show that P(A) obeys exact scaling relation P(A)=D^{1/2H}/L^{1+1/H}Φ_{H}(D^{1/2H}A/L^{1+1/H}), where 0

Current fluctuations in stochastically resetting particle systems.

We consider a system of noninteracting particles on a line with initial positions distributed uniformly with density ρ on the negative half-line. We consider two different models: (i) Each particle performs independent Brownian motion with stochastic resetting to its initial position with rate r and (ii) each particle performs run-and-tumble motion, and with rate r its position gets reset to its initial value and simultaneously its velocity gets randomized. We study the effects of resetting on the distribution P(Q,t) of the integrated particle current Q up to time t through the origin (from left to right). We study both the annealed and the quenched current distributions and in both cases, we find that resetting induces a stationary limiting distribution of the current at long times. However, we show that the approach to the stationary state of the current distribution in the annealed and the quenched cases are drastically different for both models. In the annealed case, the whole distribution P_{an}(Q,t) approaches its stationary limit uniformly for all Q. In contrast, the quenched distribution P_{qu}(Q,t) attains its stationary form for QQ_{crit}(t). We show that Q_{crit}(t) increases linearly with t for large t. On the scale where Q∼Q_{crit}(t), we show that P_{qu}(Q,t) has an unusual large deviation form with a rate function that has a third-order phase transition at the critical point. We have computed the associated rate functions analytically for both models. Using an importance sampling method that allows to probe probabilities as tiny as 10^{-14000}, we were able to compute numerically this nonanalytic rate function for the resetting Brownian dynamics and found excellent agreement with our analytical prediction.

Large-deviations of disease spreading dynamics with vaccination.

We numerically simulated the spread of disease for a Susceptible-Infected-Recovered (SIR) model on contact networks drawn from a small-world ensemble. We investigated the impact of two types of vaccination strategies, namely random vaccination and high-degree heuristics, on the probability density function (pdf) of the cumulative number C of infected people over a large range of its support. To obtain the pdf even in the range of probabilities as small as 10-80, we applied a large-deviation approach, in particular the 1/t Wang-Landau algorithm. To study the size-dependence of the pdfs within the framework of large-deviation theory, we analyzed the empirical rate function. To find out how typical as well as extreme mild or extreme severe infection courses arise, we investigated the structures of the time series conditioned to the observed values of C.

Variational kinetic clustering of complex networks.

Efficiently identifying the most important communities and key transition nodes in weighted and unweighted networks is a prevalent problem in a wide range of disciplines. Here, we focus on the optimal clustering using variational kinetic parameters, linked to Markov processes defined on the underlying networks, namely, the slowest relaxation time and the Kemeny constant. We derive novel relations in terms of mean first passage times for optimizing clustering via the Kemeny constant and show that the optimal clustering boundaries have equal round-trip times to the clusters they separate. We also propose an efficient method that first projects the network nodes onto a 1D reaction coordinate and subsequently performs a variational boundary search using a parallel tempering algorithm, where the variational kinetic parameters act as an energy function to be extremized. We find that maximization of the Kemeny constant is effective in detecting communities, while the slowest relaxation time allows for detection of transition nodes. We demonstrate the validity of our method on several test systems, including synthetic networks generated from the stochastic block model and real world networks (Santa Fe Institute collaboration network, a network of co-purchased political books, and a street network of multiple cities in Luxembourg). Our approach is compared with existing clustering algorithms based on modularity and the robust Perron cluster analysis, and the identified transition nodes are compared with different notions of node centrality.

Large deviations of a susceptible-infected-recovered model around the epidemic threshold.

We numerically study the dynamics of the SIR disease model on small-world networks by using a large-deviation approach. This allows us to obtain the probability density function of the total fraction of infected nodes and of the maximum fraction of simultaneously infected nodes down to very small probability densities like 10^{-2500}. We analyze the structure of the disease dynamics and observed three regimes in all probability density functions, which correspond to quick mild, quick extremely severe, and sustained severe dynamical evolutions, respectively. Furthermore, the mathematical rate functions of the densities are investigated. The results indicate that the so-called large-deviation property holds for the SIR model. Finally, we measured correlations with other quantities like the duration of an outbreak or the peak position of the fraction of infections, also in the rare regions which are not accessible by standard simulation techniques.

Observing symmetry-broken optimal paths of the stationary Kardar-Parisi-Zhang interface via a large-deviation sampling of directed polymers in random media.

Consider the short-time probability distribution P(H,t) of the one-point interface height difference h(x=0,τ=t)-h(x=0,τ=0)=H of the stationary interface h(x,τ) described by the Kardar-Parisi-Zhang (KPZ) equation. It was previously shown that the optimal path, the most probable history of the interface h(x,τ) which dominates the upper tail of P(H,t), is described by any of two ramplike structures of h(x,τ) traveling either to the left, or to the right. These two solutions emerge, at a critical value of H, via a spontaneous breaking of the mirror symmetry x↔-x of the optimal path, and this symmetry breaking is responsible for a second-order dynamical phase transition in the system. We simulate the interface configurations numerically by employing a large-deviation Monte Carlo sampling algorithm in conjunction with the mapping between the KPZ interface and the directed polymer in a random potential at high temperature. This allows us to observe the optimal paths, which determine each of the two tails of P(H,t), down to probability densities as small as 10^{-500}. At short times we observe mirror-symmetry-broken traveling optimal paths for the upper tail, and a single mirror-symmetric path for the lower tail, in good quantitative agreement with analytical predictions. At long times, even at moderate values of H, where the optimal fluctuation method is not supposed to apply, we still observe two well-defined dominating paths. Each of them violates the mirror symmetry x↔-x and is a mirror image of the other.

Phase transition for parameter learning of hidden Markov models.

We study a phase transition in parameter learning of hidden Markov models (HMMs). We do this by generating sequences of observed symbols from given discrete HMMs with uniformly distributed transition probabilities and a noise level encoded in the output probabilities. We apply the Baum-Welch (BW) algorithm, an expectation-maximization algorithm from the field of machine learning. By using the BW algorithm we then try to estimate the parameters of each investigated realization of an HMM. We study HMMs with n=4,8, and 16 states. By changing the amount of accessible learning data and the noise level, we observe a phase-transition-like change in the performance of the learning algorithm. For bigger HMMs and more learning data, the learning behavior improves tremendously below a certain threshold in the noise strength. For a noise level above the threshold, learning is not possible. Furthermore, we use an overlap parameter applied to the results of a maximum a posteriori (Viterbi) algorithm to investigate the accuracy of the hidden state estimation around the phase transition.

Similarity of extremely rare nonequilibrium processes to equilibrium processes.

For system coupled to heat baths, typical nonequilibrated processes, e.g., induced by varying an external parameter without waiting for equilibration in between, are very different from the corresponding equilibrium infinitely slow processes. Nevertheless, there are connections between equilibrium and nonequilibrated behaviors, e.g., the theorems of Jarzynski and Crooks, which relate the distribution P(W) of nonequilibrium work to the free energy differences ΔF. Here we study the naturally arising question, whether those relevant but rare trajectories, which exhibit these work values, show a higher degree of similarity to equilibrium. For convenience, we have chosen a simple model of RNA secondary structures (or single-stranded DNA), here modeling a medium-size hairpin structure, under influence of a varying external force. This allows us to measure the work W during the resulting fast unfolding and refolding processes within Monte Carlo simulations, i.e., in nonequilibrium. Also we sample numerically efficiently directly in exact equilibrium, for comparison. Using a sophisticated large-deviation algorithm, we are able to measure work distributions with high precision down to probabilities as small as 10^{-46}, enabling us to verify the Crooks and Jarzynski theorems. Furthermore, we analyze force-extension curves and the configurations of the secondary structures during unfolding and refolding for typical equilibrium processes and nonequilibrated processes. We find that the nonequilibrated processes where the work values are close to those which are most relevant for applying Crooks and Jarzynski theorems, respectively, but which occur with exponential small probabilities, are most and quite similar to the equilibrium processes.

Large deviations of connected components in the stochastic block model.

We study the stochastic block model, which is often used to model community structures and study community-detection algorithms. We consider the case of two blocks in regard to its largest connected component and largest biconnected component, respectively. We are especially interested in the distributions of their sizes including the tails down to probabilities smaller than 10^{-800}. For this purpose we use sophisticated Markov chain Monte Carlo simulations to sample graphs from the stochastic block model ensemble. We use these data to study the large-deviation rate function and conjecture that the large-deviation principle holds. Further we compare the distribution to the well-known Erdos-Rényi ensemble, where we notice subtle differences at and above the percolation threshold.

Easy-hard phase transition in parameter estimation for optical waveguides.

The determination of the parameters of cylindrical optical waveguides, e.g. the diameters [Formula: see text] of r layers of (semi-) transparent optical fibres, can be executed by inverse evaluation of the scattering intensities that emerge under monochromatic illumination. The inverse problem can be solved by optimising the mismatch [Formula: see text] between the measured and simulated scattering patterns. The global optimum corresponds to the correct parameter values. The mismatch [Formula: see text] can be seen as an energy landscape as a function of the diameters. In this work, we study the structure of the energy landscape for different values of the complex refractive indices [Formula: see text], for [Formula: see text] and [Formula: see text] layers. We find that for both values of r, depending on the values of [Formula: see text], two very different types of energy landscapes exist, respectively. One type is dominated by one global minimum and the other type exhibits a multitude of local minima. From an algorithmic viewpoint, this corresponds to easy and hard phases, respectively. Our results indicate that the two phases are separated by sharp phase-transition lines and that the shape of these lines can be described by one "critical" exponent b, which depends slightly on r. Interestingly, the same exponent also describes the dependence of the number of local minima on the diameters. Thus, our findings are comparable to previous theoretical studies on easy-hard transitions in basic combinatorial optimisation or decision problems like Travelling Salesperson and Satisfiability. To our knowledge our results are the first indicating the existence of easy-hard transitions for a real-world optimisation problem of technological relevance.

Percolation of Fortuin-Kasteleyn clusters for the random-bond Ising model.

We apply generalizations of the Swendson-Wang and Wolff cluster algorithms, which are based on the construction of Fortuin-Kasteleyn clusters, to the three-dimensional ±1 random-bond Ising model. The behavior of the model is determined by the temperature T and the concentration p of negative (antiferromagnetic) bonds. The ground state is ferromagnetic for 0≤p0, our data suggest that the percolation transition is universal, irrespective of whether the ground state exhibits ferromagnetic or spin-glass order, and is in the universality class of standard percolation. This shows that correlations in the bond occupancy of the Fortuin-Kasteleyn clusters are irrelevant, except for p=0 where the clusters are strictly tied to Ising correlations so the percolation transition is in the Ising universality class.

Number of longest increasing subsequences.

We study the entropy S of longest increasing subsequences (LISs), i.e., the logarithm of the number of distinct LISs. We consider two ensembles of sequences, namely, random permutations of integers and sequences drawn independent and identically distributed (i.i.d.) from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LISs for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution p(S) with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than 10^{-600}. We show that the distribution of the entropy of the LISs is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further, we propose a large-deviation rate function which fits best to our observed data.

Asymptotic behavior of the length of the longest increasing subsequences of random walks.

We numerically estimate the leading asymptotic behavior of the length L_{n} of the longest increasing subsequence of random walks with step increments following Student's t-distribution with parameters in the range 1/2≤ν≤5. We find that the expected value E(L_{n})∼n^{θ}lnn, with θ decreasing from θ(ν=1/2)≈0.70 to θ(ν≥5/2)≈0.50. For random walks with a distribution of step increments of finite variance (ν>2), this confirms previous observation of E(L_{n})∼sqrt[n]lnn to leading order. We note that this asymptotic behavior (including the subleading term) resembles that of the largest part of random integer partitions under the uniform measure and that, curiously, both random variables seem to follow Gumbel statistics. We also provide more refined estimates for the asymptotic behavior of E(L_{n}) for random walks with step increments of finite variance.

Probing large deviations of the Kardar-Parisi-Zhang equation at short times with an importance sampling of directed polymers in random media.

The one-point distribution of the height for the continuum Kardar-Parisi-Zhang equation is determined numerically using the mapping to the directed polymer in a random potential at high temperature. Using an importance sampling approach, the distribution is obtained over a large range of values, down to a probability density as small as 10^{-1000} in the tails. The short-time behavior is investigated and compared with recent analytical predictions for the large-deviation forms of the probability of rare fluctuations, showing a spectacular agreement with the analytical expressions. The flat and stationary initial conditions are studied in the full space, together with the droplet initial condition in the half-space.

Large deviations of a random walk model with emerging territories.

We study an agent-based model of animals marking their territory and evading adversarial territory in one dimension with respect to the distribution of the size of the resulting territories. In particular, we use sophisticated sampling methods to determine it over a large part of territory sizes, including atypically small and large configurations, which occur with probability of less than 10^{-30}. We find hints for the validity of a large deviation principle, the shape of the rate function for the right tail of the distribution, and insight into the structure of atypical realizations.

Large-deviations of the basin stability of power grids.

Energy grids play an important role in modern society. In recent years, there was a shift from using few central power sources to using many small power sources, due to efforts to increase the percentage of renewable energies. Therefore, the properties of extremely stable and unstable networks are of interest. In this paper, distributions of the basin stability, a nonlinear measure to quantify the ability of a power grid to recover from perturbations, and its correlations with other measurable quantities, namely, diameter, flow backup capacity, power-sign ratio, universal order parameter, biconnected component, clustering coefficient, two core, and leafs, are studied. The energy grids are modeled by an Erdos-Rényi random graph ensemble and a small-world graph ensemble, where the latter is defined in such a way that it does not exhibit dead ends. Using large-deviation techniques, we reach very improbable power grids that are extremely stable as well as ones that are extremely unstable. The 1/t-algorithm, a variation of Wang-Landau, which does not suffer from error saturation, and additional entropic sampling are used to achieve good precision even for very small probabilities ranging over eight decades.

Replica symmetry and replica symmetry breaking for the traveling salesperson problem.

We study the energy landscape of the traveling salesperson problem (TSP) using exact ground states and a novel linear programming approach to generate excited states with closely defined properties. We look at four different ensembles, notably the classic finite dimensional Euclidean TSP and the mean-field-like (1,2)-TSP, which has its origin directly in the mapping of the Hamiltonian circuit problem on the TSP. Our data supports previous conjectures that the Euclidean TSP does not show signatures of replica symmetry breaking neither in two nor in higher dimension. On the other hand the (1,2)-TSP exhibits some signature which does not exclude broken replica symmetry, making it a candidate for further studies in the future.

Large deviations of the length of the longest increasing subsequence of random permutations and random walks.

We study numerically the length distribution of the longest increasing subsequence (LIS) for random permutations and one-dimensional random walks. Using sophisticated large-deviation algorithms, we are able to obtain very large parts of the distribution, especially also covering probabilities smaller than 10^{-1000}. This enables us to verify for the length of the LIS of random permutations the analytically known asymptotics of the rate function and even the whole Tracy-Widom distribution. We observe a rather fast convergence in the larger than typical part to this limiting distribution. For the length L of LIS of random walks no analytical results are known to us. We test a proposed scaling law and observe convergence of the tails into a collapse for increasing system size. Further, we obtain estimates for the leading-order behavior of the rate functions in both tails.

Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming.

Here we study linear programming applied to the random K-SAT problem, a fundamental problem in computational complexity. The K-SAT problem is to decide whether a Boolean formula with N variables and structured as a conjunction of M clauses, each being a disjunction of K variables or their negations is satisfiable or not. The ensemble of random K-SAT attracted considerable interest from physicists because for a specific ratio αs = M/N it undergoes in the limit of large N a sharp phase transition from a satisfiable to an unsatisfiable phase. In this study we will concentrate on finding for linear programming algorithms "easy-hard" transitions between phases of different typical hardness of the problems on either side. Linear programming is widely applied to solve practical optimization problems, but has been only rarely considered in the physics community. This is a deficit, because those typically studied types of algorithms work in the space of feasible {0, 1}N configurations while linear programming operates outside the space of valid configurations hence gives a very different perspective on the typical-case hardness of a problem. Here, we demonstrate that the technique leads to one simple-to-understand transition for the well known 2-SAT problem. On the other hand we detect multiple transitions in 3-SAT and 4-SAT. We demonstrate that, in contrast to the previous work on vertex cover and therefore somewhat surprisingly, the hardness transitions are not driven by changes of any of various standard percolation or solution space properties of the problem instances. Thus, here a more complex yet undetected property must be related to the easy-hard transition.